# Author    :Dun_Hz
# Time      :2024/7/26 18:52
# 堆排序
import random


def sift(li,low,high):
    '''
    # 堆的向下调整，前提是根节点的左右子树都满足堆
    :param li: 列表
    :param low: 树的根节点
    :param high: 树的最后一个节点
    :return: ///
    '''
    i = low     #父节点
    j = 2*i+1   # 左子节点
    tmp = li[low]
    while j<=high:
        if j+1<=high and li[j+1]>li[j]:
            j = j+1
        if li[j]>tmp:
            li[i] = li[j]
            i = j
            j = 2*i+1
        else:
            break
    li[i]=tmp

def heap_sort(li):
    n=len(li)
    for i in range((n-2)//2,-1,-1):
        sift(li,i,n-1)
    # 上面for循环结束之后，堆顶为最大元素了
    for i in range(n-1,0,-1):
        li[0],li[i]=li[i],li[0]
        sift(li,0,i-1)


def topk(li,k):
    heap=li[0:k]
    # 这个循环是为了构建大根堆
    for i in range((k-2)//2,-1,-1):
        sift(heap,i,k-1)
    # 替换堆顶元素
    for i in range(k,len(li)):
        if li[i]<heap[0]:
            heap[0]=li[i]
            sift(heap,0,k-1)
    # 堆排序
    for i in range(k-1,-1,-1):
        heap[0],heap[i]=heap[i],heap[0]
        sift(heap,0,i-1)
    return heap

if __name__=="__main__":
    li = [i for i in range(15)]
    random.shuffle(li)
    print(li)

    print(topk(li,5))